package com.lw.leetcode.back.b;

import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * back
 * 1625. 执行操作后字典序最小的字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/18 17:30
 */
public class FindLexSmallestString {


    public static void main(String[] args) {
        FindLexSmallestString test = new FindLexSmallestString();

        // "2050"
        String str = "5525";
        int a = 9;
        int b = 2;

        // "00553311"
//        String str = "43987654";
//        int a = 7;
//        int b = 3;

        String lexSmallestString = test.findLexSmallestString(str, a, b);
        System.out.println(lexSmallestString);
    }

    private Set<String> set = new HashSet<>();

    public String findLexSmallestString(String s, int a, int b) {
        char[] chars = s.toCharArray();
        set.add(s);
        find(chars, a, b);
        return set.stream().min(Comparator.naturalOrder()).get();
    }

    private void find(char[] chars, int a, int b) {
        int length = chars.length;
        char[] ns = new char[length];
        System.arraycopy(chars, 0, ns, 0, length);
        add(ns, a);
        String s = String.valueOf(ns);
        if (!set.contains(s)) {
            set.add(s);
            find(ns, a, b);
        }
        System.arraycopy(chars, 0, ns, 0, length);
        change(ns, b);
        s = String.valueOf(ns);
        if (!set.contains(s)) {
            set.add(s);
            find(ns, a, b);
        }
    }

    private void add(char[] chars, int a) {
        int length = chars.length;
        int c = a - 10;
        for (int i = 1; i < length; i+=2) {
            chars[i] = (char) (chars[i] + a > '9' ? chars[i] + c : chars[i] + a);
        }
    }

    private void change(char[] chars, int b) {
        int length = chars.length;
        int st = 0;
        int end = length - 1;
        ch(chars, st, end);
        end = b - 1;
        ch(chars, st, end);
        st = b;
        end = length - 1;
        ch(chars, st, end);
    }

    private void ch(char[] chars, int st, int end) {
        int m = st + ((end - st) >> 1);
        char t;
        int c = 0;
        for (int i = st; i <= m; i++) {
            t = chars[i];
            chars[i] = chars[end - c];
            chars[end - c] = t;
            c++;
        }
    }

}
